#include "order_tree.h"
#include "link_tree.h"

void _add_ot(TreeNode** tree, TreeNode* node)
{
    if(NULL == *tree) {
        *tree = node;
        return;
    }
    if(node->data < (*tree)->data) {
        _add_ot(&(*tree)->left,node);
    }else{
        _add_ot(&(*tree)->right,node);
    }
    cal_height_lt(*tree);
}

void add_ot(TreeNode** tree, void* data)
{
    _add_ot(tree,create_tn(data,0));
}

bool del_ot(TreeNode** tree, void* data,CMP cmp)
{
    if(NULL == *tree)return false;
    if(0 > cmp(data,(*tree)->data)){
        return del_ot(&(*tree)->left,data,cmp);
    }
    if(0 < cmp(data,(*tree)->data)){
        return del_ot(&(*tree)->right,data,cmp);
    }
    TreeNode* tmp = *tree;
    *tree = tmp->right;
    if(tmp->left)_add_ot(tree,tmp->left);
    free(tmp);
    return true;
}

bool mod_val_ot(TreeNode** tree, void* old_data, void* new_data,CMP cmp)
{
    if(del_ot(tree,old_data,cmp)){
        add_ot(tree,new_data);
        return true;
    }
    return false;
}

TreeNode* _query_val_ot(TreeNode* tree, void* data,CMP cmp)
{
    if(NULL == tree)return NULL;
    if(0 < cmp(tree->data,data)){
        return _query_val_ot(tree->left,data,cmp);
    }
    if(0 > cmp(tree->data,data)){
        return _query_val_ot(tree->right,data,cmp);
    }
    return tree;
}

void* query_val_ot(TreeNode* tree, void* data,CMP cmp)
{
    TreeNode* node = _query_val_ot(tree,data,cmp);
    return node->data;
}

void rdl_last_k_ot(TreeNode* tree, int* index,FUNC show)
{
    if(NULL == tree)return;
    rdl_last_k_ot(tree->right,index,show);
    if(--(*index) == 0)show(tree->data);
    rdl_last_k_ot(tree->left,index,show);
}

TreeNode *prev = NULL;

void _create_cot(TreeNode* tree)
{
    if(!tree)return;
    _create_cot(tree->left);
//    if(!tree->left){
//        tree->hasLeftClue = true;
//        tree->left = prev;
//    }
    if(prev && !prev->right){
        prev->hasRightClue = true;
        prev->right = tree;
    }
    prev = tree;
    _create_cot(tree->right);
}

void create_cot(TreeNode* tree)
{
    _create_cot(tree);
}

void clue_cot(TreeNode* tree,FUNC show)
{
    while(NULL != tree){
        while(NULL != tree->left){
            tree = tree->left;
        }
        show(tree->data);
        while(tree->hasRightClue){
            tree = tree->right;
            show(tree->data);
        }
        tree = tree->right;
    }
}

void cal_height_lt(TreeNode* root)
{
    if(!root)return;
    int lh = height_lt(root->left);
    int rh = height_lt(root->right);
    root->height = lh>rh?lh+1:rh+1;
}
